package com.sice.common.test;

import org.apache.commons.lang3.StringUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static void main(String[] args) {
        //[5,4,6,null,null,3,7]
        // 3,1,0,2,5,4,7

        TreeNode node1 = new TreeNode(1, new TreeNode(0), new TreeNode(2));
        TreeNode node2 = new TreeNode(5, new TreeNode(4), new TreeNode(7));
        TreeNode node = new TreeNode(3, node1, node2);
        System.out.println(isValidBST(node));

        ListNode listNode = new ListNode(5);
        ListNode a = new ListNode(4, listNode);
        ListNode b = new ListNode(3, a);
        ListNode c = new ListNode(2, b);
        ListNode d = new ListNode(1, c);
        System.out.println(removeNthFromEnd(d, 2).val);

        System.out.println(le2("bbacdefbaiklzcsa"));

        boolean b1 = checkInclusion("BAC", "bbcaswABCsdA");
        System.out.println(b1);

    }

    /**
     * s2  中包含  s1 的字母组合(无序)
     */
    public static boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m=s2.length();
        if(n>m) {
            return false;
        }
        //仅包含小写字母
        int[] index1 = new int[64];
        int[] index2 = new int[64];
        for(int i=0;i<n;i++) {
            ++index1[s1.charAt(i)-'A'];
            ++index2[s2.charAt(i)-'A'];
        }
        if(Arrays.equals(index1, index2)) {
            return true;
        }
        for(int i=n;i<m;i++) {
            index2[s2.charAt(i)-'A']++;
            index2[s2.charAt(i-n)-'A']--;
            if(Arrays.equals(index1, index2)) {
                return true;
            }
        }
        return false;

    }

    public static int le2(String s) {
        int maxLength = 0;
        int length = 0;
        Map<Integer, Integer> tmpArray = new HashMap<>();
        for(int i=0;i<s.length();i++) {
            int index = s.charAt(i);
            length = Math.max(tmpArray.getOrDefault(index, 0), length);
            maxLength = Math.max(maxLength, i-length+1);
            tmpArray.put(index, i+1);
        }
        return maxLength;
    }


    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int length = 0;
        int[] tmpArray = new int[128];
        for(int i=0;i<s.length();i++) {
            int index = s.charAt(i);
            length = Math.max(tmpArray[index], length);
            maxLength = Math.max(maxLength, i-length+1);
            tmpArray[index] = i+1;
        }
        return maxLength;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head, fast = head;

        while(n-- !=0) {
            fast = fast.next;
        }
        if(fast==null) {
            return head.next;
        }
        fast = fast.next;
        while(fast!=null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }


    static public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    static int minValue = Integer.MIN_VALUE;

    public static boolean isValidBST(TreeNode root) {
        //左节点必定小于根节点，右节点大于根节点
        if(root == null) {
            return true;
        }
//        System.out.println("前序遍历："+root.val);
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val<=minValue) {
            return false;
        }
        minValue = root.val;
        boolean validBST = isValidBST(root.right);
//        System.out.println("后序遍历："+root.val);
        return validBST;
    }

    //      Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
